package LeetCode1;

import java.util.HashMap;
import java.util.Map;

//判断平衡树
public class Num110 {
    private Map<TreeNode, Integer> nodeHeight = new HashMap<>();

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 判断当前以root为根节点的树是否满足平衡条件
        int left = 0;
        int right = 0;
        if (nodeHeight.containsKey(root.left)) {
            // 此时左树的高度已经被计算过了，直接从map中取出节点值对于的高度
            left = nodeHeight.get(root.left);
        } else {
            left = hight(root.left);
            // 将该节点和对于的高度存入Map中
            nodeHeight.put(root.left, left);
        }
        if (nodeHeight.containsKey(root.right)) {
            right = nodeHeight.get(root.right);
        } else {
            right = hight(root.right);
            nodeHeight.put(root.right, right);
        }
        int abs = Math.abs(right - left);
        if (abs > 1) {
            return false;
        }
        // 继续递归判断左树要满足平衡 并且 右树也要满足平衡
        return isBalanced(root.left) && isBalanced(root.right);
    }

    private int hight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(hight(root.left), hight(root.right));
    }
}
